Compression schemes, such as Lempel-Ziv based compression schemes (for example, LZ77 and LZ78) are often used in a data centers to compress data, thereby enabling compute devices in the data center to store more customer data in a given amount of data storage capacity and/or transmit more customer data in a given amount of network bandwidth. When compressing data pursuant to a Lempel-Ziv based scheme, the compute device searches for the longest string from a history buffer (e.g., a sliding window of previous data from an input stream) that matches a string starting at the present position in the input stream (e.g., a number of bytes into the input stream). To do so, the compute device typically produces a hash by performing a hashing function on a symbol (e.g., a byte or other unit of data) at the present position and one or more subsequent symbols in the input stream, and uses the resulting hash as an index into a hash table that includes, for each hash, a set of pointers that point to other strings in the history buffer that produced the same hash.
The compute device, in typical compression systems, then compares one or more of the strings associated with the pointers found in the hash table to the string at the present position to find one or more matches, and selects the longest matching string. To increase the level of compression, the compute device may compare a larger number of the possible matching strings to the present string, to increase the possibility of finding a longer matching string. When a suitable (e.g., long enough to satisfy a predefined threshold) matching string is found, the compute device replaces the literal symbols (e.g., the actual data) of the string starting at the present position with a much smaller (e.g., in terms of data size) reference back to the matched string, along with a length identifier, representing the amount of the matched string to reproduce at the present position. While increasing the number of strings to be compared against the string starting at the present position in an input stream may increase the compression of the data, it also increases the amount of time required to compress the input data.